package demo.ybt;


public class P1261_2 {
    public static void main(String[] args) {
        P1261_2 p1261 = new P1261_2();
        int res = p1261.res(new int[][]{
                {0, 2, 5, 1, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 12, 14, 0, 0, 0, 0},
                {0, 0, 0, 0, 6, 10, 4, 0, 0, 0},
                {0, 0, 0, 0, 13, 12, 11, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 3, 9, 0},
                {0, 0, 0, 0, 0, 0, 0, 6, 5, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 10, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 5},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 2},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
        });
        System.out.println(res);
    }

    public int res(int[][] t) {

        int dp[] = new int[t.length];
        int h = t.length;
        int w = h;

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (t[i][j] > 0) {
                    //dp[j]= dp[i]+t[i][j];
                    if (i == 0 ||dp[i] > 0) {
                        //如果dp[j]==0代表 j元素之前没来过，所以直接更新上
                        //如果 dp[i] + t[i][j] 这个路径更小，也更新dp[j]
                        if (dp[j] == 0 || dp[j] > dp[i] + t[i][j]) {
                            dp[j] = dp[i] + t[i][j];
                        }
                        //dp[j]=dp[i]+t[i][j];
                    }
                }
            }
        }

        return dp[t.length - 1];

    }
}
